package ljl.alg.jianzhioffer.round2;

import java.util.PriorityQueue;

/**
 * 在知道怎么做的情况下做错了！
 * 不是失误，就是不会！
 * ！
 * */
public class _41_median_of_stream {
    
    /**
     * 我知道咋做，两个堆
     * 这不是我想到的，是我见多识广才知道的
     * 背过也是一种能力，虽然是一种低级能力
     * 低能
     *
     * 1. 总是 min 的数量 >= max
     * 2. 偶数，去 max 的最大值
     * 3. 奇数，去两者平均值
     * 4. 添加时，总是往 min 里添加，然后把最小的放到 max 里
     * */
    static class MedianFinder {
        
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>((a, b) -> b - a);
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        int count;
        
        // 不管在哪个堆里放数，都要经过两个堆的过滤
        public void addNum(int num) {
            
            /*
            // 这么写也行，但是有点脱裤子放屁
            minQueue.offer(num);
            count++;
            maxQueue.offer(minQueue.poll());
            if ((count & 1) == 1) {
                minQueue.offer(maxQueue.poll());
            }*/
            count++;
            if ((count & 1) == 0) {
                minQueue.offer(num);
                maxQueue.offer(minQueue.poll());
            } else {
                maxQueue.offer(num);
                minQueue.offer(maxQueue.poll());
            }
        }
    
        // 1 2 3 4 5
        public double findMedian() {
            if ((count & 1) == 0) {
                return (minQueue.peek() + maxQueue.peek()) / 2.0;
            }
            return minQueue.peek();
        }
    }
    
}
